{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #两数相除"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: divide"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两数相除"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个整数 <code>a</code> 和 <code>b</code> ，求它们的除法的商 <code>a/b</code> ，要求不得使用乘号 <code>&#39;*&#39;</code>、除号 <code>&#39;/&#39;</code> 以及求余符号 <code>&#39;%&#39;</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>整数除法的结果应当截去（<code>truncate</code>）其小数部分，例如：<code>truncate(8.345) = 8</code>&nbsp;以及&nbsp;<code>truncate(-2.7335) = -2</code></li>\n",
    "\t<li>假设我们的环境只能存储 32 位有符号整数，其数值范围是 <code>[&minus;2<sup>31</sup>,&nbsp;2<sup>31</sup>&minus;1]</code>。本题中，如果除法结果溢出，则返回 <code>2<sup>31&nbsp;</sup>&minus; 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 15, b = 2\n",
    "<strong>输出：</strong>7\n",
    "<strong><span style=\"white-space: pre-wrap;\">解释：</span></strong>15/2 = truncate(7.5) = 7\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 7, b = -3\n",
    "<strong>输出：</strong><span style=\"white-space: pre-wrap;\">-2</span>\n",
    "<strong><span style=\"white-space: pre-wrap;\">解释：</span></strong>7/-3 = truncate(-2.33333..) = -2</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 0, b = 1\n",
    "<strong>输出：</strong><span style=\"white-space: pre-wrap;\">0</span></pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 1, b = 1\n",
    "<strong>输出：</strong><span style=\"white-space: pre-wrap;\">1</span></pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-2<sup>31</sup>&nbsp;&lt;= a, b &lt;= 2<sup>31</sup>&nbsp;- 1</code></li>\n",
    "\t<li><code>b != 0</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 29&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/divide-two-integers/\">https://leetcode-cn.com/problems/divide-two-integers/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [xoh6Oh](https://leetcode.cn/problems/xoh6Oh/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [xoh6Oh](https://leetcode.cn/problems/xoh6Oh/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['15\\n2', '7\\n-3', '-7\\n3', '0\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makesquare(self, matchsticks: List[int]) -> bool:\n",
    "        bucket = [0] * 4\n",
    "        nums = sorted(matchsticks, reverse=True)\n",
    "        if sum(nums) % 4 != 0:\n",
    "            return False\n",
    "        target = sum(nums) // 4\n",
    "        select = 0\n",
    "        st = set()\n",
    "        def divide(b_indx):\n",
    "            nonlocal select\n",
    "            if b_indx == 4:\n",
    "                return True\n",
    "            for i in range(0, len(nums)):\n",
    "                if select & (1 << i) != 0:\n",
    "                    continue\n",
    "                bucket[b_indx] += nums[i]\n",
    "                select += (1 << i)\n",
    "                if select in st:\n",
    "                    select -= (1 << i)\n",
    "                    bucket[b_indx] -= nums[i]\n",
    "                    continue\n",
    "                if bucket[b_indx] < target:\n",
    "                    if divide(b_indx):\n",
    "                        return True\n",
    "                    st.add(select)\n",
    "                if bucket[b_indx] == target:\n",
    "                    if divide(b_indx + 1):\n",
    "                        return True\n",
    "                    st.add(select)\n",
    "                select -= (1 << i)\n",
    "                bucket[b_indx] -= nums[i]\n",
    "            return False\n",
    "        return divide(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        return int(self.right_bound(k) - self.left_bound(k) + 1)\n",
    "    \n",
    "\n",
    "\n",
    "    def trailingzero(self, n):\n",
    "        res = 0\n",
    "        divider = 5\n",
    "        while n >= divider:\n",
    "            res += n // divider\n",
    "            n = n //divider\n",
    "        return res\n",
    "    \n",
    "\n",
    "\n",
    "    def left_bound(self, target):\n",
    "        left, right = 0, 2**63 - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.trailingzero(mid) >= target:\n",
    "                right = mid - 1\n",
    "            elif self.trailingzero(mid) < target:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return left\n",
    "    \n",
    "\n",
    "    def right_bound(self, target):\n",
    "        left, right = 0, 2**63 - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.trailingzero(mid) <= target:\n",
    "                left = mid + 1\n",
    "            elif self.trailingzero(mid) > target:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left - 1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        ret = 0\n",
    "        flag = False if (a > 0 and b > 0) or (a < 0 and b < 0) else True\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        def calc(x, y):\n",
    "            n = 1\n",
    "            while x > y << 1:\n",
    "                y <<= 1\n",
    "                n <<= 1\n",
    "            return n, y\n",
    "\n",
    "        while a >= b:\n",
    "            cnt, val = calc(a, b)\n",
    "            ret += cnt\n",
    "            a -= val\n",
    "        ret = -ret if flag else ret\n",
    "        return ret - 1 if ret >= 2 ** 31 else ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        num_min,num_max=-2**31,2**31-1\n",
    "        ne=2\n",
    "        if a == num_min:\n",
    "            if b == 1:\n",
    "                return num_min\n",
    "            if b == -1:\n",
    "                return num_max\n",
    "        count=0\n",
    "        if a<0:\n",
    "            ne-=1\n",
    "            a1=-a\n",
    "        else:\n",
    "            a1=a\n",
    "        if b<0:\n",
    "            ne-=1\n",
    "            b=-b\n",
    "        for i in range(32,-1,-1):\n",
    "            \n",
    "            if a1>=b*(2**i):\n",
    "                a1-=b*(2**i)\n",
    "                count += 2**i\n",
    "        \n",
    "        if ne%2!=0:\n",
    "            count=-count\n",
    "        return count\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if (a>=0 and b>=0) or (a<0 and b<0): flag = False\n",
    "        else: flag = True\n",
    "        a, b = abs(a), abs(b)\n",
    "        res = 0\n",
    "        while a>=b:\n",
    "            n = 1\n",
    "            t = b\n",
    "            while a > (t<<1):\n",
    "                n <<= 1\n",
    "                t <<= 1 \n",
    "            a -= t\n",
    "            res += n\n",
    "        \n",
    "        if flag: res = -res\n",
    "\n",
    "        return res if -2**31 <=res <= 2**31-1 else 2**31 - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        #位运算+二分查找\n",
    "        if (a>=0 and b>=0) or (a<0 and b<0):flag=False\n",
    "        else:flag=True\n",
    "        #flag表示是否a,b异号，这样求出来的就可以直接添加负号\n",
    "        a,b=abs(a),abs(b)\n",
    "        res=0\n",
    "        while a>=b:\n",
    "            n=1\n",
    "            t=b\n",
    "            while a>(t<<1):\n",
    "                n<<=1# a大于多少个b\n",
    "                t<<=1\n",
    "            a-=t\n",
    "            res+=n\n",
    "        if flag:res=-res\n",
    "        return res if -2**31 <=res <=2**31-1 else 2**31-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if a == -2**31 and b == -1:\n",
    "            return 2**31 - 1\n",
    "        positive = (a > 0) == (b > 0)\n",
    "        a, b, res = abs(a), abs(b), 0\n",
    "        for i in range(31, -1, -1):\n",
    "            # 2^i * b <= a\n",
    "            if (b << i) <= a:\n",
    "                res += 1 << i\n",
    "                a -= b << i\n",
    "        return res if positive else -res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        # 特殊情况\n",
    "        if b == 1:\n",
    "            return a\n",
    "        if a == 0:\n",
    "            return a\n",
    "        \n",
    "        # 正负号\n",
    "        neg_flag = False\n",
    "        if (a < 0 and b > 0) or (a > 0 and b < 0):\n",
    "            neg_flag = True\n",
    "        a = abs(a)\n",
    "        b = abs(b)\n",
    "        \n",
    "        # 得到和\n",
    "        times = [1]\n",
    "        values = [b]\n",
    "        while a >= values[-1]:\n",
    "            times.append(times[-1] + times[-1])\n",
    "            values.append(values[-1] + values[-1])\n",
    "        \n",
    "        # print(times, values, a, b)\n",
    "        # 计算a/b\n",
    "        residual = a\n",
    "        ans = 0\n",
    "        index = len(values) -  1\n",
    "        while residual != 0:\n",
    "            while index >= 0 and residual < values[index]:\n",
    "                index -= 1\n",
    "            if index < 0:\n",
    "                residual = 0\n",
    "                break\n",
    "            residual -= values[index]\n",
    "            ans += times[index]\n",
    "        \n",
    "        if neg_flag:\n",
    "           ans = -ans\n",
    "        if ans < - 2 ** 31 or ans > 2 ** 31 - 1:\n",
    "            ans = 2 ** 31 - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        ret = 0\n",
    "        flag = False if (a > 0 and b>0) or (a <0 and b < 0) else True\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        def calc(x, y):\n",
    "            n = 1\n",
    "            while x > y << 1:\n",
    "                y <<=1\n",
    "                n <<=1\n",
    "            return n, y\n",
    "        \n",
    "        while a >= b:\n",
    "            cnt , val = calc(a, b)\n",
    "            ret += cnt\n",
    "            a -= val\n",
    "        ret = -ret if flag else ret\n",
    "        return ret -1 if ret >=2 ** 31 else ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        cur=abs (a) // abs (b) * (-1 if ((a>0)!=( b>0)) else 1)\n",
    "        if(cur>2**31-1):\n",
    "            return 2**31-1\n",
    "        elif(cur<-2**31):\n",
    "            return -2**31\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        \n",
    "        if a == - (1 << 31) and b == -1:\n",
    "            return 0x7fffffff\n",
    "\n",
    "        flag = True\n",
    "        if a < 0:\n",
    "            a = -a\n",
    "            flag = False\n",
    "        \n",
    "        if b < 0:\n",
    "            b = -b\n",
    "            flag = not flag\n",
    "\n",
    "        left, right = 0, a + 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mid * b <= a:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left - 1 if flag else -(left - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        x=math.trunc(a/b)\n",
    "        return x if x <=2**31-1 else 2**31-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        ret = 0\n",
    "        flag = False if (a > 0 and b > 0) or (a < 0 and b < 0) else True\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        def calc(x, y):\n",
    "            n = 1\n",
    "            while x > y << 1:\n",
    "                y <<= 1\n",
    "                n <<= 1\n",
    "            return n, y\n",
    "\n",
    "        while a >= b:\n",
    "            cnt, val = calc(a, b)\n",
    "            ret += cnt\n",
    "            a -= val\n",
    "        ret = -ret if flag else ret\n",
    "        return ret - 1 if ret >= 2 ** 31 else ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        i, a, b = 0, abs(dividend), abs(divisor)\n",
    "        if a == 0 or a < b:\n",
    "            return 0\n",
    "        \n",
    "        while b <= a:\n",
    "            b = b << 1\n",
    "            i = i + 1\n",
    "        else:\n",
    "            res = (1 << (i - 1)) + self.divide(a - (b >> 1), abs(divisor))\n",
    "            if (dividend ^ divisor) < 0:\n",
    "                res = -res\n",
    "        return min(res, (1 << 31) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "INT_MAX = (1<<31)-1\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        sign = 1\n",
    "        if dividend * divisor < 0:\n",
    "            dividend, divisor = abs(dividend), abs(divisor)\n",
    "            sign = -1\n",
    "        return min(INT_MAX, dividend // divisor * sign)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        flag = True if (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0) else False\n",
    "        dividend, divisor = abs(dividend), abs(divisor)\n",
    "\n",
    "        res = 0\n",
    "        while dividend >= divisor:\n",
    "           a, b = self.calc(dividend, divisor)\n",
    "           dividend = dividend - a\n",
    "           res = res + b\n",
    "        res = res if flag else -res\n",
    "        return res - 1 if res >= 2 ** 31 else res\n",
    "\n",
    "    # 20, 3 -> 12, 4\n",
    "    def calc(self, dividend, divisor):\n",
    "        a = 1\n",
    "        while dividend >= (divisor + divisor):\n",
    "            divisor = divisor + divisor\n",
    "            a = a + a\n",
    "        return divisor, a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, _a: int, _b: int) -> int:\n",
    "        if _a == 0:\n",
    "            return 0\n",
    "        a, b = abs(_a), abs(_b) \n",
    "        #倍增\n",
    "        ans = 0\n",
    "        for i in range(32, -1, -1):\n",
    "            t = b << i\n",
    "            if t <= a:\n",
    "                a -= t\n",
    "                ans |= 1 << i\n",
    "        return min((1 << 31) - 1, ans) if (_a > 0 and _b > 0) or (_a < 0 and _b < 0) else -ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        # 先判断符号情况\n",
    "        if (a >= 0 and b >= 0) or (a < 0 and b < 0):\n",
    "            flag = False\n",
    "        else:\n",
    "            flag = True\n",
    "        a,b = abs(a),abs(b)\n",
    "        res = 0\n",
    "\n",
    "        while (a >= b):\n",
    "            n = 1\n",
    "            t = b\n",
    "            while a > (t << 1):\n",
    "                n <<= 1 # a 大于 b几倍\n",
    "                t <<= 1\n",
    "            a -= t\n",
    "            res += n\n",
    "\n",
    "        if flag:\n",
    "            res = -res\n",
    "        return res if -2 ** 31 <= res <= 2 ** 31 - 1 else 2 ** 31 - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if int(a / b) > 2147483647:\n",
    "            return 2147483647\n",
    "        else:\n",
    "            return int(a / b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        # 当被除数大于除数时，除数翻倍，直至除数大于被除数\n",
    "        # 记录翻倍的次数\n",
    "        res = 0\n",
    "        flag = False if (a<0 and b<0) or (a>0 and b>0) else True\n",
    "        a, b = abs(a), abs(b)\n",
    "        \n",
    "        def calc(x, y):\n",
    "            # 计数器\n",
    "            n = 1\n",
    "            while x > y<<1:\n",
    "                y <<= 1\n",
    "                n <<= 1\n",
    "            return n, y\n",
    "        \n",
    "        while a >= b:\n",
    "            cnt, val = calc(a, b)\n",
    "            res += cnt\n",
    "            a -= val\n",
    "        \n",
    "        # 判断正负号\n",
    "        res = -res if flag else res\n",
    "\n",
    "        return res - 1 if res >= 2**31 else res\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        res = 0\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        \n",
    "        if (a > 0 and b < 0) or (a < 0 and b> 0):\n",
    "            sign = -1\n",
    "        \n",
    "        if (a < 0 and b < 0) or (a > 0 and b > 0):\n",
    "            sign = 1\n",
    "        \n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        target = a\n",
    "        \n",
    "        while target >= b:  \n",
    "            t, cnt = b, 1\n",
    "            while target >= (t + t):\n",
    "                cnt += cnt\n",
    "                t += t\n",
    "            res += cnt\n",
    "            target -= t\n",
    "        res = sign * res\n",
    "        if -2**31 <= res <= 2**31-1:\n",
    "            return res\n",
    "        else:\n",
    "            return 2**31-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend, divisor):\n",
    "        positive = (dividend < 0) is (divisor < 0)\n",
    "        dividend, divisor = abs(dividend), abs(divisor)\n",
    "        res = 0\n",
    "        while dividend >= divisor:\n",
    "            temp, i = divisor, 1\n",
    "            while dividend >= temp:\n",
    "                dividend -= temp\n",
    "                res += i\n",
    "                i <<= 1\n",
    "                temp <<= 1\n",
    "        if not positive:\n",
    "            res = -res\n",
    "        return min(max(-2147483648, res), 2147483647)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def divide(self, a: int, b: int) -> int:\r\n",
    "        if (a >= 0 and b>=0) or (a<0 and b<0):\r\n",
    "            condition = -1\r\n",
    "        else:\r\n",
    "            condition = 1\r\n",
    "        if a > 0:\r\n",
    "            c = -a\r\n",
    "        else:\r\n",
    "            c = a\r\n",
    "        if b > 0:\r\n",
    "            d = -b\r\n",
    "        else:\r\n",
    "            d = b\r\n",
    "        n = 0\r\n",
    "        while (c <= d):\r\n",
    "            t = 1\r\n",
    "            tmp = d\r\n",
    "            while (c - tmp <= tmp):\r\n",
    "                tmp <<= 1\r\n",
    "                t <<= 1\r\n",
    "            c -= tmp\r\n",
    "            n += t\r\n",
    "        if condition > 0:\r\n",
    "            n = -n\r\n",
    "        if n >= 2147483648:\r\n",
    "            n = 2147483647\r\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        t=int(a/b)\n",
    "        if -2**31<=t<=2**31-1: return t\n",
    "        return 2**31-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        int_max = 2 ** 31 - 1\n",
    "        int_min = -2 ** 31\n",
    "\n",
    "        def helper(large, small):\n",
    "            if large < small:\n",
    "                return 0\n",
    "            \n",
    "            cnt = 1\n",
    "            tmp_small = small\n",
    "            while tmp_small + tmp_small <= large:\n",
    "                tmp_small += tmp_small\n",
    "                cnt += cnt\n",
    "            \n",
    "            return cnt + helper(large - tmp_small, small)\n",
    "        \n",
    "        if a == int_min and b == -1:\n",
    "            return int_max\n",
    "        \n",
    "        sign = 1\n",
    "        if (a > 0 > b) or (a < 0 < b):\n",
    "            sign = -1\n",
    "        \n",
    "        a, b = abs(a), abs(b)\n",
    "        tot = helper(a, b)\n",
    "\n",
    "        if int_min <= sign * tot <= int_max:\n",
    "            return sign * tot\n",
    "        else:\n",
    "            return int_max\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "         INT_MIN, INT_MAX = -2**31, 2**31 - 1 \n",
    "         if (a < 0 and b > 0) or (a > 0 and b < 0):\n",
    "             flag = -1\n",
    "         elif a == 0:\n",
    "             flag = 0\n",
    "         else:\n",
    "             flag = 1    \n",
    "         a = a if a > 0 else -a            \n",
    "         b = b if b > 0 else -b\n",
    "         \n",
    "         if a < b:\n",
    "             return 0\n",
    "         ans = 1    \n",
    "         sum = b\n",
    "         while sum+sum <= a:\n",
    "             sum += sum\n",
    "             ans += ans\n",
    "         ans += self.divide(a-sum, b)    \n",
    "         if flag < 0:\n",
    "            ans = -ans\n",
    "         if ans < INT_MIN:\n",
    "             ans = INT_MIN  \n",
    "         elif ans >  INT_MAX:\n",
    "             ans = INT_MAX   \n",
    "         return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if a == -2147483648 and b == -1:\n",
    "            return 2147483647\n",
    "        div_sum = 0\n",
    "        flag = True\n",
    "        if a < 0:\n",
    "            flag = not flag\n",
    "            a = abs(a)\n",
    "        if b < 0:\n",
    "            flag = not flag\n",
    "            b = abs(b)\n",
    "\n",
    "        while a >= b:\n",
    "            i = 0\n",
    "            tmp = b\n",
    "            while b << i <= a:\n",
    "                tmp = b << i\n",
    "                i += 1\n",
    "            a -= tmp\n",
    "            div_sum += 1 << (i-1)\n",
    "\n",
    "        if flag:\n",
    "            return div_sum\n",
    "        else:\n",
    "            return -div_sum\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if a==0:\n",
    "            return 0\n",
    "        sign=1 if (a>0 and b>0 or a<0 and b<0) else -1\n",
    "        a,b=abs(a),abs(b)\n",
    "        ans=0\n",
    "        while a>=b:\n",
    "            c=b\n",
    "            bit=1\n",
    "            while a>c+c:\n",
    "                c+=c\n",
    "                bit+=bit\n",
    "            a-=c\n",
    "            ans+=bit\n",
    "        if sign==1:\n",
    "            return min(ans,2147483647)\n",
    "        else:\n",
    "            return -ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        INT_MIN, INT_MAX = -2**31, 2**31 - 1\n",
    "\n",
    "        # 考虑被除数为最小值的情况\n",
    "        if a == INT_MIN:\n",
    "            if b == 1:\n",
    "                return INT_MIN\n",
    "            if b == -1:\n",
    "                return INT_MAX\n",
    "        \n",
    "        # 考虑除数为最小值的情况\n",
    "        if b == INT_MIN:\n",
    "            return 1 if a == INT_MIN else 0\n",
    "        # 考虑被除数为 0 的情况\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        \n",
    "        # 一般情况，使用二分查找\n",
    "        # 将所有的正数取相反数，这样就只需要考虑一种情况\n",
    "        rev = False\n",
    "        if a > 0:\n",
    "            a = -a\n",
    "            rev = not rev\n",
    "        if b > 0:\n",
    "            b = -b\n",
    "            rev = not rev\n",
    "\n",
    "        # 快速乘\n",
    "        def quickAdd(y: int, z: int, x: int) -> bool:\n",
    "            # x 和 y 是负数，z 是正数\n",
    "            # 需要判断 z * y >= x 是否成立\n",
    "            result, add = 0, y\n",
    "            while z > 0:\n",
    "                if (z & 1) == 1:\n",
    "                    # 需要保证 result + add >= x\n",
    "                    if result < x - add:\n",
    "                        return False\n",
    "                    result += add\n",
    "                if z != 1:\n",
    "                    # 需要保证 add + add >= x\n",
    "                    if add < x - add:\n",
    "                        return False\n",
    "                    add += add\n",
    "                # 不能使用除法\n",
    "                z >>= 1\n",
    "            return True\n",
    "        \n",
    "        left, right, ans = 1, INT_MAX, 0\n",
    "        while left <= right:\n",
    "            # 注意溢出，并且不能使用除法\n",
    "            mid = left + ((right - left) >> 1)\n",
    "            check = quickAdd(b, mid, a)\n",
    "            if check:\n",
    "                ans = mid\n",
    "                # 注意溢出\n",
    "                if mid == INT_MAX:\n",
    "                    break\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return -ans if rev else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        # 位运算 + 二分查找\n",
    "        if (a>=0 and b>=0) or (a<0 and b<0): flag = False\n",
    "        else: flag = True\n",
    "        # flag表示是否a,b异号\n",
    "        a, b = abs(a), abs(b)\n",
    "        res = 0\n",
    "        while a>=b:\n",
    "            n = 1\n",
    "            t = b\n",
    "            while a > (t<<1):\n",
    "                n <<= 1 # a大于多少个b\n",
    "                t <<= 1 \n",
    "            a -= t\n",
    "            res += n\n",
    "        \n",
    "        if flag: res = -res\n",
    "\n",
    "        return res if -2**31 <=res <= 2**31-1 else 2**31 - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        INT_MIN, INT_MAX = -2**31, 2**31 - 1\n",
    "\n",
    "        # 考虑被除数为最小值的情况\n",
    "        if a == INT_MIN:\n",
    "            if b == 1:\n",
    "                return INT_MIN\n",
    "            if b == -1:\n",
    "                return INT_MAX\n",
    "        \n",
    "        # 考虑除数为最小值的情况\n",
    "        if b == INT_MIN:\n",
    "            return 1 if a == INT_MIN else 0\n",
    "        # 考虑被除数为 0 的情况\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        \n",
    "        # 一般情况，使用二分查找\n",
    "        # 将所有的正数取相反数，这样就只需要考虑一种情况\n",
    "        rev = False\n",
    "        if a > 0:\n",
    "            a = -a\n",
    "            rev = not rev\n",
    "        if b > 0:\n",
    "            b = -b\n",
    "            rev = not rev\n",
    "\n",
    "        # 快速乘\n",
    "        def quickAdd(y: int, z: int, x: int) -> bool:\n",
    "            # x 和 y 是负数，z 是正数\n",
    "            # 需要判断 z * y >= x 是否成立\n",
    "            result, add = 0, y\n",
    "            while z > 0:\n",
    "                if (z & 1) == 1:\n",
    "                    # 需要保证 result + add >= x\n",
    "                    if result < x - add:\n",
    "                        return False\n",
    "                    result += add\n",
    "                if z != 1:\n",
    "                    # 需要保证 add + add >= x\n",
    "                    if add < x - add:\n",
    "                        return False\n",
    "                    add += add\n",
    "                # 不能使用除法\n",
    "                z >>= 1\n",
    "            return True\n",
    "        \n",
    "        left, right, ans = 1, INT_MAX, 0\n",
    "        while left <= right:\n",
    "            # 注意溢出，并且不能使用除法\n",
    "            mid = left + ((right - left) >> 1)\n",
    "            check = quickAdd(b, mid, a)\n",
    "            if check:\n",
    "                ans = mid\n",
    "                # 注意溢出\n",
    "                if mid == INT_MAX:\n",
    "                    break\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return -ans if rev else ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unsignedDivide(self, a: int, b: int) -> int:\n",
    "        \"\"\" 正数除法 \"\"\"\n",
    "        div = 0\n",
    "        while a >= b:\n",
    "            # b_times == b*bit, bit == 2**n\n",
    "            bit, b_times = 1, b\n",
    "            while a >= b_times:\n",
    "                div += bit\n",
    "                a -= b_times\n",
    "                bit <<= 1\n",
    "                b_times <<= 1\n",
    "        return div\n",
    "\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        # 溢出的情况只有一种: -2**31 / -1\n",
    "        if a == -(1 << 31) and b == -1:\n",
    "            return (1 << 31) - 1\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        if (a > 0) == (b > 0):\n",
    "            return self.unsignedDivide(abs(a), abs(b))\n",
    "        else:\n",
    "            return -self.unsignedDivide(abs(a), abs(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        ret = 0 \n",
    "        flag=False if a*b<0 else True\n",
    "        a,b=abs(a),abs(b)\n",
    "        def cal(x,y):\n",
    "            n=1\n",
    "            while x>y<<1:\n",
    "                y<<=1\n",
    "                n<<=1\n",
    "            return n,y\n",
    "        while a>=b:\n",
    "            cnt,val=cal(a,b)\n",
    "            ret+=cnt\n",
    "            a-=val\n",
    "        ret = (-1)*ret if flag==False else ret\n",
    "        return ret-1 if ret>=2**31 else ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unsignedDivide(self, a: int, b: int) -> int:\n",
    "        \"\"\" 正数除法 \"\"\"\n",
    "        div = 0\n",
    "        while a >= b:\n",
    "            # b_times == b*bit, bit == 2**n\n",
    "            bit, b_times = 1, b\n",
    "            while a >= b_times:\n",
    "                div += bit\n",
    "                a -= b_times\n",
    "                bit <<= 1\n",
    "                b_times <<= 1\n",
    "        return div\n",
    "\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        # 溢出的情况只有一种: -2**31 / -1\n",
    "        if a == -(1 << 31) and b == -1:\n",
    "            return (1 << 31) - 1\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        if (a > 0) == (b > 0):\n",
    "            return self.unsignedDivide(abs(a), abs(b))\n",
    "        else:\n",
    "            return -self.unsignedDivide(abs(a), abs(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        ret = 0\n",
    "        flag = True if (a > 0 and b > 0) or (a < 0 and b < 0) else False\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        def calc(x, y):\n",
    "            n = 1\n",
    "            while x > y << 1:\n",
    "                y <<= 1\n",
    "                n <<= 1\n",
    "            return n, y\n",
    "\n",
    "        while a >= b:\n",
    "            cnt, val = calc(a, b)\n",
    "            ret += cnt\n",
    "            a -= val\n",
    "        ret = ret if flag else -ret\n",
    "        return ret - 1 if ret >= 2 ** 31 else ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if (a<0 and b>0 and a%b!=0)or(a>0 and b<0 and a%b!=0):\n",
    "            t=a//b+1\n",
    "        else:\n",
    "            t=a//b\n",
    "        if t>=-2**31 and t<=2**31-1:\n",
    "            return t\n",
    "        else:\n",
    "            return 2**31-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        INT_MIN, INT_MAX = -2**31, 2**31 - 1\n",
    "\n",
    "        # 考虑被除数为最小值的情况\n",
    "        if a == INT_MIN:\n",
    "            if b == 1:\n",
    "                return INT_MIN\n",
    "            if b == -1:\n",
    "                return INT_MAX\n",
    "        \n",
    "        # 考虑除数为最小值的情况\n",
    "        if b == INT_MIN:\n",
    "            return 1 if a == INT_MIN else 0\n",
    "\n",
    "        # 考虑被除数为 0 的情况\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        \n",
    "        # 一般情况，使用二分查找\n",
    "        # 将所有的正数取相反数，这样就只需要考虑一种情况\n",
    "        rev = False\n",
    "        if a > 0:\n",
    "            a = -a\n",
    "            rev = not rev\n",
    "            \n",
    "        if b > 0:\n",
    "            b = -b\n",
    "            rev = not rev\n",
    "\n",
    "        # 快速乘\n",
    "        def quickAdd(y: int, z: int, x: int) -> bool:\n",
    "            # x 和 y 是负数，z 是正数\n",
    "            # 需要判断 z * y >= x 是否成立\n",
    "            result, add = 0, y\n",
    "            while z > 0:\n",
    "                if (z & 1) == 1:\n",
    "                    # 需要保证 result + add >= x\n",
    "                    if result < x - add:\n",
    "                        return False\n",
    "                    result += add\n",
    "                if z != 1:\n",
    "                    # 需要保证 add + add >= x\n",
    "                    if add < x - add:\n",
    "                        return False\n",
    "                    add += add\n",
    "                # 不能使用除法\n",
    "                z >>= 1\n",
    "            return True\n",
    "        \n",
    "        left, right, ans = 1, INT_MAX, 0\n",
    "        while left <= right:\n",
    "            # 注意溢出，并且不能使用除法\n",
    "            mid = left + ((right - left) >> 1)\n",
    "            check = quickAdd(b, mid, a)\n",
    "            if check:\n",
    "                ans = mid\n",
    "                # 注意溢出\n",
    "                if mid == INT_MAX:\n",
    "                    break\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return -ans if rev else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if a == -2147483648 and b == -1: return 2147483647\n",
    "        return int(a/b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if a == 0: return 0\n",
    "        flag = False if (a > 0 and b < 0) or (a < 0 and b > 0) else True\n",
    "        res = 0\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        def cal(a, b):\n",
    "            n = 1\n",
    "            while b << 1 < a:\n",
    "                b <<= 1\n",
    "                n <<= 1\n",
    "            return b, n\n",
    "\n",
    "        while a >= b:\n",
    "            val, n = cal(a, b)\n",
    "            res += n\n",
    "            a -= val\n",
    "        \n",
    "        res = res if flag else -res\n",
    "        return res if -2 **31 <= res <= 2 ** 31 - 1 else 2 ** 31 -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        ret = 0\n",
    "        flag = False if (a > 0 and b > 0) or (a < 0 and b < 0) else True\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        def calc(x, y):\n",
    "            n = 1\n",
    "            while x > y << 1:\n",
    "                y <<= 1\n",
    "                n <<= 1\n",
    "            return n, y\n",
    "\n",
    "        while a >= b:\n",
    "            cnt, val = calc(a, b)\n",
    "            ret += cnt\n",
    "            a -= val\n",
    "        ret = -ret if flag else ret\n",
    "        return ret - 1 if ret >= 2 ** 31 else ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        \n",
    "         if a== -2147483648 and b == -1:\n",
    "            return 2147483647 \n",
    "         if abs(a+b)!=abs(a)+abs(b):\n",
    "            \n",
    "            return -self.divide(abs(a),abs(b))\n",
    "         if a<0 and b<0:\n",
    "            return self.divide(-a,-b)\n",
    "         if a<b:\n",
    "            return 0\n",
    "         if abs(len(str(a)) - len(str(b))) < 3:\n",
    "            n=1\n",
    "            while a-b>=b:\n",
    "               a=a-b\n",
    "               n=n+1\n",
    "               \n",
    "            return n\n",
    "         result=0\n",
    "         astr=str(a)\n",
    "         x=len(str(b))\n",
    "         use = int(astr[:x])\n",
    "         res = self.divide(use, b) \n",
    "         use=use-res*b\n",
    "         result = result * 10 + res\n",
    "         for i in astr[x:]:\n",
    "            use = use * 10 + int(i) # 每一次添上下一位\n",
    "            res = self.divide(use, b) # 因为 a 和 b 比较接近可以直接用相减的办法\n",
    "            use -= res * b # 减去这一位的值\n",
    "            result = result * 10 + res\n",
    "         return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if a > 0:\n",
    "            if b > 0:\n",
    "                sign = 1\n",
    "            else:\n",
    "                sign = -1\n",
    "        else:\n",
    "            if b > 0:\n",
    "                sign = -1\n",
    "            else:\n",
    "                sign = 1\n",
    "        a = abs(a)\n",
    "        b = abs(b)\n",
    "        if a < b:\n",
    "            return 0\n",
    "        out = 1\n",
    "        c = b\n",
    "        while c+c <= a:\n",
    "            out <<= 1\n",
    "            c += c\n",
    "        out += self.divide(a-c, b)\n",
    "        out = sign*out\n",
    "        return out if (out >= -2**31) and (out < 2**31) else 2**31-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if int(a/b) > 2**31 - 1:\n",
    "            return 2**31 - 1\n",
    "        elif int(a/b) < -2**31:\n",
    "            return -2**31\n",
    "        else:\n",
    "            return int(a/b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        nb = abs(b)\n",
    "        na = abs(a)\n",
    "        if a == -2147483648 and b == -1:\n",
    "            return (2 << 30) - 1\n",
    "        div = 0\n",
    "        left = na\n",
    "        while left >= nb:\n",
    "            t = nb\n",
    "            id_two = 0\n",
    "            while (t + t) <= left:\n",
    "                t = t + t\n",
    "                id_two += 1\n",
    "            div += 1 << id_two\n",
    "            left -= t\n",
    "\n",
    "        if (nb == b) == (na == a):\n",
    "                return div\n",
    "        else:\n",
    "                return (0 - div)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        a = int(a/b)\n",
    "        if -2**31 <= a <= 2**31-1:\n",
    "            return a\n",
    "        return 2**31-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        ret = 0\n",
    "        flag = False if (a > 0 and b > 0) or (a < 0 and b < 0) else True\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        def calc(x, y):\n",
    "            n = 1\n",
    "            while x > y << 1:\n",
    "                y <<= 1\n",
    "                n <<= 1\n",
    "            return n, y\n",
    "\n",
    "        while a >= b:\n",
    "            cnt, val = calc(a, b)\n",
    "            ret += cnt\n",
    "            a -= val\n",
    "        ret = -ret if flag else ret\n",
    "        return ret - 1 if ret >= 2 ** 31 else ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        flag = False if (a > 0 and b < 0) or (a < 0 and b > 0) else True\n",
    "        res = 0\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        def cal(a, b):\n",
    "            n = 1\n",
    "            while b << 1 < a:\n",
    "                b <<= 1\n",
    "                n <<= 1\n",
    "            return b, n\n",
    "\n",
    "        while a >= b:\n",
    "            val, n = cal(a, b)\n",
    "            res += n\n",
    "            a -= val\n",
    "        \n",
    "        res = res if flag else -res\n",
    "        return res if -2 **31 <= res <= 2 ** 31 - 1 else 2 ** 31 -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        cnt = 0\n",
    "        flag = (a>0 and b>0) or (a<0 and b<0)\n",
    "        if a == -2**31 and  b == -1:\n",
    "            print(a,b)\n",
    "            return 2**31-1\n",
    "        \n",
    "        if a>0:\n",
    "            a=-a\n",
    "        if b>0:\n",
    "            b=-b\n",
    "        res = 0\n",
    "        while a<=b:\n",
    "            cnt = -1\n",
    "            temp = b\n",
    "            while temp >= float(\"-inf\")/2 and a<= temp + temp:\n",
    "                temp += temp\n",
    "                cnt += cnt\n",
    "            a -= temp\n",
    "            res+=cnt\n",
    "        if flag:\n",
    "            return -res\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        res=0\n",
    "        if (a<0 and b>0) or (a>0 and b<0):\n",
    "            flag=1\n",
    "        else:\n",
    "            flag=0\n",
    "        a=abs(a)\n",
    "        b=abs(b)\n",
    "\n",
    "        if a<b: return 0\n",
    "\n",
    "        while a>=b:\n",
    "            # res+=1\n",
    "            # a=a-b\n",
    "            # # print(a,b)\n",
    "\n",
    "            n=1 #b的n倍\n",
    "            t=b\n",
    "            while a>(t<<1):\n",
    "                n=n<<1\n",
    "                t=t<<1\n",
    "            \n",
    "            a=a-t\n",
    "            res+=n\n",
    "\n",
    "\n",
    "        if flag:\n",
    "            res=-res\n",
    "        return res if -2**31<=res<=2**31-1 else 2**31-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        INT_MIN, INT_MAX = -2**31, 2**31 - 1\n",
    "\n",
    "        # 考虑被除数为最小值的情况\n",
    "        if a == INT_MIN:\n",
    "            if b == 1:\n",
    "                return INT_MIN\n",
    "            if b == -1:\n",
    "                return INT_MAX\n",
    "        \n",
    "        # 考虑除数为最小值的情况\n",
    "        if b == INT_MIN:\n",
    "            return 1 if a == INT_MIN else 0\n",
    "\n",
    "        # 考虑被除数为 0 的情况\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        \n",
    "        # 一般情况，使用二分查找\n",
    "        # 将所有的正数取相反数，这样就只需要考虑一种情况\n",
    "        rev = False\n",
    "        if a > 0:\n",
    "            a = -a\n",
    "            rev = True\n",
    "            \n",
    "        if b > 0:\n",
    "            b = -b\n",
    "            rev = not rev\n",
    "\n",
    "        # 快速乘\n",
    "        def quickAdd(y: int, z: int, x: int) -> bool:\n",
    "            # x 和 y 是负数，z 是正数\n",
    "            # 需要判断 z * y >= x 是否成立\n",
    "            result, add = 0, y\n",
    "            while z > 0:\n",
    "                if (z & 1) == 1:\n",
    "                    # 需要保证 result + add >= x\n",
    "                    if result < x - add:\n",
    "                        return False\n",
    "                    result += add\n",
    "                if z != 1:\n",
    "                    # 需要保证 add + add >= x\n",
    "                    if add < x - add:\n",
    "                        return False\n",
    "                    add += add\n",
    "                # 不能使用除法\n",
    "                z >>= 1\n",
    "            return True\n",
    "        \n",
    "        left, right, ans = 1, INT_MAX, 0\n",
    "        while left <= right:\n",
    "            # 注意溢出，并且不能使用除法\n",
    "            mid = left + ((right - left) >> 1)\n",
    "            check = quickAdd(b, mid, a)\n",
    "            if check:\n",
    "                ans = mid\n",
    "                # 注意溢出\n",
    "                if mid == INT_MAX:\n",
    "                    break\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return -ans if rev else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        ans = 0\n",
    "        flag = False if (a>0 and b>0) or (a<0 and b<0) else True\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        def calc(x, y):\n",
    "            n = 1\n",
    "            while x > y<<1:\n",
    "                y <<= 1\n",
    "                n <<= 1\n",
    "            return n, y\n",
    "        \n",
    "        while a>=b:\n",
    "            cnt, val = calc(a, b)\n",
    "            ans += cnt\n",
    "            a -= val\n",
    "        ans = -ans if flag else ans\n",
    "        return ans-1 if ans >= 2 ** 31 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        flag = (a < 0 and b < 0) or (a >= 0 and b >= 0)\n",
    "        res = 0\n",
    "        a, b = abs(a), abs(b)\n",
    "        while a >= b:\n",
    "            n = 1\n",
    "            t = b\n",
    "            while a > (t << 1):\n",
    "                n <<= 1\n",
    "                t <<= 1\n",
    "            res += n\n",
    "            a -= t\n",
    "        if not flag: res = -res\n",
    "\n",
    "        return res if -2 ** 31 <= res <= 2 ** 31 - 1 else 2 ** 31 - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def divide(self, a: int, b: int) -> int:\r\n",
    "        if a <= -2147483648 and b>=-1 and b<0:\r\n",
    "            return 2147483647\r\n",
    "        if (a >= 0 and b>=0) or (a<0 and b<0):\r\n",
    "            condition = -1\r\n",
    "        else:\r\n",
    "            condition = 1\r\n",
    "        if a > 0:\r\n",
    "            c = -a\r\n",
    "        else:\r\n",
    "            c = a\r\n",
    "        if b > 0:\r\n",
    "            d = -b\r\n",
    "        else:\r\n",
    "            d = b\r\n",
    "        n = 0\r\n",
    "        while (c <= d):\r\n",
    "            t = 1\r\n",
    "            tmp = d\r\n",
    "            while (c - tmp <= tmp):\r\n",
    "                tmp <<= 1\r\n",
    "                t <<= 1\r\n",
    "            c -= tmp\r\n",
    "            n += t\r\n",
    "        if condition > 0:\r\n",
    "            n = -n\r\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if -1*2**31<=a/b<=2**31-1:\n",
    "            return int(a/b)\n",
    "        return 2**31-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        ans = 0\n",
    "        flag = True\n",
    "        if (a > 0 and b > 0) or (a < 0 and b < 0):\n",
    "            flag = False\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        def cal(x, y):\n",
    "            n = 1\n",
    "            while x > y << 1:\n",
    "                y <<= 1\n",
    "                n <<= 1\n",
    "            return n, y\n",
    "        \n",
    "        while a >= b:\n",
    "            cnt, val = cal(a, b)\n",
    "            ans += cnt\n",
    "            a -= val\n",
    "        ans = -ans if flag else ans\n",
    "        return ans - 1 if ans >= 2 ** 31 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        limit = 2147483647\n",
    "        if a == -2147483648 and b == -1:\n",
    "            return limit\n",
    "        sign = 1 if (a > 0) == (b > 0) else -1\n",
    "        a, b = abs(a), abs(b)\n",
    "        res = 0\n",
    "        while a >= b:\n",
    "            x, y = b, 1\n",
    "            while a >= x << 1:\n",
    "                x <<= 1\n",
    "                y <<= 1\n",
    "            a -= x\n",
    "            res += y\n",
    "        return res * sign"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        INT_MIN, INT_MAX = -2**31, 2**31 - 1\n",
    "\n",
    "        # 考虑被除数为最小值的情况\n",
    "        if a == INT_MIN:\n",
    "            if b == 1:\n",
    "                return INT_MIN\n",
    "            if b == -1:\n",
    "                return INT_MAX\n",
    "        \n",
    "        # 考虑除数为最小值的情况\n",
    "        if b == INT_MIN:\n",
    "            return 1 if a == INT_MIN else 0\n",
    "        # 考虑被除数为 0 的情况\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        \n",
    "        # 一般情况，使用类二分查找\n",
    "        # 将所有的正数取相反数，这样就只需要考虑一种情况\n",
    "        rev = False\n",
    "        if a > 0:\n",
    "            a = -a\n",
    "            rev = not rev\n",
    "        if b > 0:\n",
    "            b = -b\n",
    "            rev = not rev\n",
    "        \n",
    "        candidates = [b]\n",
    "        # 注意溢出\n",
    "        while candidates[-1] >= a - candidates[-1]:\n",
    "            candidates.append(candidates[-1] + candidates[-1])\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(candidates) - 1, -1, -1):\n",
    "            if candidates[i] >= a:\n",
    "                ans += (1 << i)\n",
    "                a -= candidates[i]\n",
    "\n",
    "        return -ans if rev else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        INT_MIN, INT_MAX = -2**31, 2**31 - 1\n",
    "\n",
    "        # 考虑被除数为最小值的情况\n",
    "        if a == INT_MIN:\n",
    "            if b == 1:\n",
    "                return INT_MIN\n",
    "            if b == -1:\n",
    "                return INT_MAX\n",
    "        \n",
    "        # 考虑除数为最小值的情况\n",
    "        if b == INT_MIN:\n",
    "            return 1 if a == INT_MIN else 0\n",
    "        # 考虑被除数为 0 的情况\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        \n",
    "        # 一般情况，使用类二分查找\n",
    "        # 将所有的正数取相反数，这样就只需要考虑一种情况\n",
    "        rev = False\n",
    "        if a > 0:\n",
    "            a = -a\n",
    "            rev = not rev\n",
    "        if b > 0:\n",
    "            b = -b\n",
    "            rev = not rev\n",
    "        \n",
    "        candidates = [b]\n",
    "        # 注意溢出\n",
    "        while candidates[-1] >= a - candidates[-1]:\n",
    "            candidates.append(candidates[-1] + candidates[-1])\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(candidates) - 1, -1, -1):\n",
    "            if candidates[i] >= a:\n",
    "                ans += (1 << i)\n",
    "                a -= candidates[i]\n",
    "\n",
    "        return -ans if rev else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unsignedDivide(self, a: int, b: int) -> int:\n",
    "        \"\"\" 正数除法 \"\"\"\n",
    "        div = 0\n",
    "        while a >= b:\n",
    "            # b_times == b*bit, bit == 2**n\n",
    "            bit, b_times = 1, b\n",
    "            while a >= b_times:\n",
    "                div += bit\n",
    "                a -= b_times\n",
    "                bit <<= 1\n",
    "                b_times <<= 1\n",
    "        return div\n",
    "\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        # 溢出的情况只有一种: -2**31 / -1\n",
    "        if a == -(1 << 31) and b == -1:\n",
    "            return (1 << 31) - 1\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        if (a > 0) == (b > 0):\n",
    "            return self.unsignedDivide(abs(a), abs(b))\n",
    "        else:\n",
    "            return -self.unsignedDivide(abs(a), abs(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        # 不让用符号想实现功能，第一反应位运算\n",
    "        bound=2**31\n",
    "        \n",
    "        # 其中一种溢出情况\n",
    "        if b == 0:\n",
    "            return 2**31-1\n",
    "\n",
    "        # 确定最终答案符号\n",
    "        if a>0 and b>0 or a<0 and b<0:\n",
    "            flag = 1\n",
    "        else:\n",
    "            flag = -1\n",
    "        \n",
    "        c,d = abs(a),abs(b)\n",
    "\n",
    "        # 找出最大可移动的位数，并减去b<<maxshift,则当前得到的结果为1<<maxshift\n",
    "        def pre(a,b):\n",
    "            if a<b:\n",
    "                return 0\n",
    "            if a==b:\n",
    "                return 1\n",
    "            maxshift = 0\n",
    "            tmp = b\n",
    "            while tmp<a:\n",
    "                tmp<<=1\n",
    "                maxshift+=1\n",
    "            maxshift-=1\n",
    "            return (1<<maxshift)+pre(a-(b<<maxshift),b)\n",
    "        res = flag*pre(c,d)\n",
    "\n",
    "        # 根据题目的溢出条件返回相应的值\n",
    "        if -bound<=res<=bound-1:\n",
    "            return res\n",
    "        return bound-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if a == -pow(2, 31) and b == -1:\n",
    "            return pow(2, 31) - 1\n",
    "        elif a == 0:\n",
    "            return 0\n",
    "        elif b == 1:\n",
    "            return a\n",
    "        elif b == -1:\n",
    "            return -a\n",
    "\n",
    "        if a < 0:\n",
    "            a = -a\n",
    "            b = -b\n",
    "        if b < 0:\n",
    "            sym = -1\n",
    "            b = -b\n",
    "        else:\n",
    "            sym = 1\n",
    "        \n",
    "        ans = ''\n",
    "        r = ''\n",
    "        sa = str(a)\n",
    "        for s in sa:\n",
    "            ans += '0'\n",
    "            r += s\n",
    "            r = int(r)\n",
    "            t = 0\n",
    "            while r >= b:\n",
    "                r -= b\n",
    "                t += 1\n",
    "            r = str(r)\n",
    "            ans = str(int(ans)+t)\n",
    "        ans = int(ans)\n",
    "        return ans if sym == 1 else -ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if (a == -2 ** 31 and b == 1) or (a == 2 ** 31 and b == -1):return -2 ** 31\n",
    "        if (a < 0 and b > 0) or (a > 0 and b < 0): return -self.divide(abs(a), abs(b))\n",
    "        elif a < 0 and b < 0: return self.divide(-a, -b)\n",
    "\n",
    "        b_ = b\n",
    "        while a > b_:\n",
    "            b_ <<= 1\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while b_ >= b:\n",
    "            if a >= b_:\n",
    "                a -= b_\n",
    "                res += 1\n",
    "            elif b_ == b:\n",
    "                break\n",
    "            else:\n",
    "                b_ >>= 1\n",
    "                res *= 2\n",
    "        \n",
    "        return res if res < 2 ** 31 else 2 ** 31 - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if a == 0 or b == 1: \n",
    "            return a\n",
    "        if a == -2147483648 and b == -1:\n",
    "            return 2147483647\n",
    "        ans = 0\n",
    "        flag = -1 if a*b < 0 else 1\n",
    "        a = -abs(a)\n",
    "        b = -abs(b)\n",
    "        while a <= b:\n",
    "            t = 1\n",
    "            s = b\n",
    "            while a - s <= s:\n",
    "                s += s\n",
    "                t += t\n",
    "            ans += t\n",
    "            a -= s\n",
    "            print(a,b)\n",
    "        return ans * flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        INT_MIN, INT_MAX = -2**31, 2**31 - 1\n",
    "\n",
    "        # 考虑被除数为最小值的情况\n",
    "        if a == INT_MIN:\n",
    "            if b == 1:\n",
    "                return INT_MIN\n",
    "            if b == -1:\n",
    "                return INT_MAX\n",
    "        \n",
    "        # 考虑除数为最小值的情况\n",
    "        if b == INT_MIN:\n",
    "            return 1 if a == INT_MIN else 0\n",
    "        # 考虑被除数为 0 的情况\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        \n",
    "        # 一般情况，使用二分查找\n",
    "        # 将所有的正数取相反数，这样就只需要考虑一种情况\n",
    "        rev = False\n",
    "        if a > 0:\n",
    "            a = -a\n",
    "            rev = not rev\n",
    "        if b > 0:\n",
    "            b = -b\n",
    "            rev = not rev\n",
    "\n",
    "        # 快速乘\n",
    "        def quickAdd(y: int, z: int, x: int) -> bool:\n",
    "            # x 和 y 是负数，z 是正数\n",
    "            # 需要判断 z * y >= x 是否成立\n",
    "            result, add = 0, y\n",
    "            while z > 0:\n",
    "                if (z & 1) == 1:\n",
    "                    # 需要保证 result + add >= x\n",
    "                    if result < x - add:\n",
    "                        return False\n",
    "                    result += add\n",
    "                if z != 1:\n",
    "                    # 需要保证 add + add >= x\n",
    "                    if add < x - add:\n",
    "                        return False\n",
    "                    add += add\n",
    "                # 不能使用除法\n",
    "                z >>= 1\n",
    "            return True\n",
    "        \n",
    "        left, right, ans = 1, INT_MAX, 0\n",
    "        while left <= right:\n",
    "            # 注意溢出，并且不能使用除法\n",
    "            mid = left + ((right - left) >> 1)\n",
    "            check = quickAdd(b, mid, a)\n",
    "            if check:\n",
    "                ans = mid\n",
    "                # 注意溢出\n",
    "                if mid == INT_MAX:\n",
    "                    break\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return -ans if rev else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        # 处理特殊情况\n",
    "        INT_MIN, INT_MAX = -1<<31, (1<<31) - 1\n",
    "        if a == INT_MIN:\n",
    "            if b == 1:\n",
    "                return INT_MIN\n",
    "            if b == -1:\n",
    "                return INT_MAX\n",
    "\n",
    "        # 确定符号\n",
    "        flag = 1 if (a >= 0 and b >= 0) or (a < 0 and b < 0) else -1\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        # 找到最高位\n",
    "        pos = 1\n",
    "        multiply_b = b\n",
    "        while multiply_b < a:\n",
    "            multiply_b <<= 1\n",
    "            pos <<= 1\n",
    "\n",
    "        # 从最高位往低位依次累加\n",
    "        res = 0\n",
    "        while pos > 0:\n",
    "            if a >= multiply_b:\n",
    "                res += pos\n",
    "                a -= multiply_b\n",
    "\n",
    "            pos >>= 1\n",
    "            multiply_b >>= 1\n",
    "        \n",
    "        return res if flag == 1 else -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        # 处理特殊情况\n",
    "        INT_MIN, INT_MAX = -1<<31, (1<<31) - 1\n",
    "        if a == INT_MIN:\n",
    "            if b == 1:\n",
    "                return INT_MIN\n",
    "            if b == -1:\n",
    "                return INT_MAX\n",
    "        if b == INT_MIN:\n",
    "            return 1 if a == INT_MIN else 0\n",
    "\n",
    "        # 确定符号\n",
    "        flag = 1 if (a >= 0 and b >= 0) or (a < 0 and b < 0) else -1\n",
    "        a, b = abs(a), abs(b)\n",
    "\n",
    "        # 找到最高位\n",
    "        pos = 1\n",
    "        multiply_b = b\n",
    "        while multiply_b < a:\n",
    "            multiply_b <<= 1\n",
    "            pos <<= 1\n",
    "\n",
    "        # 从最高位往低位依次累加\n",
    "        res = 0\n",
    "        while pos > 0:\n",
    "            if a >= multiply_b:\n",
    "                res += pos\n",
    "                a -= multiply_b\n",
    "\n",
    "            pos >>= 1\n",
    "            multiply_b >>= 1\n",
    "        \n",
    "        return res if flag == 1 else -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        # 简单概括为： 60/8 = (60-32)/8 + 4 = (60-32-16)/8 + 2 + 4 = 1 + 2 + 4 = 7\n",
    "        def div(a, b):\n",
    "            if a < b:\n",
    "                return 0\n",
    "\n",
    "            # 计算a里面有几个b\n",
    "            multiple = 1\n",
    "            tmp = b\n",
    "            while tmp+tmp <= a:\n",
    "                tmp += tmp # b的值翻倍递增\n",
    "                multiple += multiple # b的个数也翻倍\n",
    "\n",
    "            # 剩下的不足一倍了，再次重复递归，直到a<b为止\n",
    "            return multiple + div(a-tmp, b)\n",
    "\n",
    "        positive = True if (a > 0 and b > 0) or (a < 0 and b < 0) else False\n",
    "        a = a if a > 0 else -a\n",
    "        b = b if b > 0 else -b\n",
    "\n",
    "        res = div(a, b)\n",
    "        res = res if positive else -res\n",
    "        if res < -2**31:\n",
    "            return -2**31\n",
    "        elif res > 2**31-1:\n",
    "            return 2**31-1\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        if a==0:\n",
    "            return 0\n",
    "        minus=False\n",
    "        if (a>0 and b<0) or (a<0 and b>0):\n",
    "            minus=True\n",
    "        a=abs(a)\n",
    "        b=abs(b)\n",
    "\n",
    "        ans=0\n",
    "        while a>=b:\n",
    "            temp=b\n",
    "            digit=1\n",
    "            while temp<=a:\n",
    "                temp=temp<<1\n",
    "                digit=digit<<1\n",
    "            ans+=(digit>>1)\n",
    "            a-=(temp>>1)\n",
    "        ans=-ans if minus else ans\n",
    "        return ans if -2**31<=ans<=2**31-1 else 2**31-1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        c=0\n",
    "        if a==0:\n",
    "            return a\n",
    "        if a>=2**31-1:\n",
    "            if b==1:\n",
    "                return 2**31-1\n",
    "            elif b==-1:\n",
    "                return -2**31\n",
    "        elif a<=-2**31:\n",
    "            if b==1:\n",
    "                return -2**31\n",
    "            elif b==-1:\n",
    "                return 2**31-1\n",
    "        if a>0:\n",
    "            if b>0:\n",
    "                c=a//b\n",
    "            else:\n",
    "                c=(a+b+1)//b\n",
    "        else:\n",
    "            if b>0:\n",
    "                c=(a+b-1)//b\n",
    "            else:\n",
    "                c=a//b\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        min_value = -2**31\n",
    "        max_value = 2 **31 - 1\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        if a == min_value and b == -1:\n",
    "            return max_value\n",
    "        flag = True\n",
    "        if a > 0 and b < 0 or a < 0 and b > 0:\n",
    "            flag = False\n",
    "\n",
    "        \n",
    "        def help(x, y):\n",
    "            if x < y:\n",
    "                return 0\n",
    "            cnt = 1\n",
    "            ty = y\n",
    "            while ty + ty < x:\n",
    "                cnt = 2*cnt\n",
    "                ty = 2*ty\n",
    "            return cnt + help(x - ty, y)\n",
    "        return help(abs(a), abs(b)) if flag else - help(abs(a), abs(b))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "\n",
    "        INT_MIN, INT_MAX = -2**31, 2**31 - 1\n",
    "        dividend = a\n",
    "        divisor = b\n",
    "        # 考虑被除数为最小值的情况\n",
    "        if dividend == INT_MIN:\n",
    "            if divisor == 1:\n",
    "                return INT_MIN\n",
    "            if divisor == -1:\n",
    "                return INT_MAX\n",
    "        \n",
    "        # 考虑除数为最小值的情况\n",
    "        if divisor == INT_MIN:\n",
    "            return 1 if dividend == INT_MIN else 0\n",
    "        # 考虑被除数为 0 的情况\n",
    "        if dividend == 0:\n",
    "            return 0\n",
    "        \n",
    "        # 一般情况，使用二分查找\n",
    "        # 将所有的正数取相反数，这样就只需要考虑一种情况\n",
    "        rev = False\n",
    "        if dividend > 0:\n",
    "            dividend = -dividend\n",
    "            rev = not rev\n",
    "        if divisor > 0:\n",
    "            divisor = -divisor\n",
    "            rev = not rev\n",
    "\n",
    "        # 快速乘\n",
    "        def quickAdd(y: int, z: int, x: int) -> bool:\n",
    "            # x 和 y 是负数，z 是正数\n",
    "            # 需要判断 z * y >= x 是否成立\n",
    "            result, add = 0, y\n",
    "            while z > 0:\n",
    "                if (z & 1) == 1:\n",
    "                    # 需要保证 result + add >= x\n",
    "                    if result < x - add:\n",
    "                        return False\n",
    "                    result += add\n",
    "                if z != 1:\n",
    "                    # 需要保证 add + add >= x\n",
    "                    if add < x - add:\n",
    "                        return False\n",
    "                    add += add\n",
    "                # 不能使用除法\n",
    "                z >>= 1\n",
    "            return True\n",
    "        \n",
    "        left, right, ans = 1, INT_MAX, 0\n",
    "        while left <= right:\n",
    "            # 注意溢出，并且不能使用除法\n",
    "            mid = left + ((right - left) >> 1)\n",
    "            check = quickAdd(divisor, mid, dividend)\n",
    "            if check:\n",
    "                ans = mid\n",
    "                # 注意溢出\n",
    "                if mid == INT_MAX:\n",
    "                    break\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return -ans if rev else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, a: int, b: int) -> int:\n",
    "        ans = 0\n",
    "        if a >= 0 and b >= 0 or a <= 0 and b <= 0: flag = 1\n",
    "        else: flag = -1\n",
    "        a, b = abs(a), abs(b)\n",
    "        \n",
    "        def calc(x, y):\n",
    "            n = 1\n",
    "            while x > y << 1:\n",
    "                y <<= 1\n",
    "                n <<= 1\n",
    "            return n, y\n",
    "        \n",
    "        while a >= b:\n",
    "            cnt, val = calc(a, b)\n",
    "            ans += cnt\n",
    "            a -= val\n",
    "        ans = flag * ans\n",
    "        return ans - 1 if ans >= 2 ** 31 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        \"\"\"\n",
    "        注意：在Python中，//向下取整，int()向零取整。\n",
    "\n",
    "        根据题意，对于两个负数X与Y，为求 X / Y，我们需要找到非负数X使得\n",
    "            Z Y >= X > (Z+1) Y\n",
    "        因此可以使用二分查找的方式找到最大Z使得 Z Y >= X 成立。\n",
    "        \"\"\"\n",
    "        # Python3中整数是任意长度的\n",
    "        INTMAX = (2<<30)-1\n",
    "        INTMIN = -(2<<30)\n",
    "\n",
    "        if divisor == 1:\n",
    "            return dividend\n",
    "        elif divisor == -1:\n",
    "            if dividend == INTMIN:\n",
    "                return INTMAX\n",
    "            return -dividend\n",
    "        elif dividend == 0:\n",
    "            return 0\n",
    "\n",
    "        negsign = False\n",
    "        \n",
    "        # 负数的范围更大！\n",
    "        if dividend > 0:\n",
    "            negsign = not negsign\n",
    "            dividend = - dividend\n",
    "        if divisor > 0:\n",
    "            negsign = not negsign\n",
    "            divisor = - divisor\n",
    "        \n",
    "        if dividend > divisor:\n",
    "            return 0\n",
    "        \n",
    "        def check(z, y, x):\n",
    "            result, add = 0, y\n",
    "            while z > 0:\n",
    "                if (z & 1) == 1:\n",
    "                    if result < x - add:\n",
    "                        return False\n",
    "                    result += add\n",
    "                if z != 1:\n",
    "                    if add < x - add:\n",
    "                        return False\n",
    "                    add += add\n",
    "                z >>= 1\n",
    "            return True\n",
    "\n",
    "        # 到此，我们已经判断完结果为0，INTMIN的情况\n",
    "        left, right = 1, INTMAX\n",
    "        while left <= right:\n",
    "            mid = left + ((right - left) >> 1)\n",
    "            if check(mid, divisor, dividend):\n",
    "                ans = mid\n",
    "                if mid == INTMAX:\n",
    "                    break\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return -ans if negsign else ans\n",
    "                    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
